The invention relates to data processing in which the degree of resemblance between a data sample and interpolations between another data sample and further data samples is determined for each interpolation. The invention may be applied in, for example, video encoding that employs half-pixel motion estimation.
It is possible to determine the degree of resemblance between a data sample and interpolations between another data sample and further data samples in the following manner. In a first step, the interpolations are calculated. For example, an interpolation may be the other data sample multiplied by a first weighting factor and a further data sample multiplied by a second weighting factor. In a second step, differences between the data sample and the interpolations are calculated for each interpolation. It seems that the United Kingdom patent application published under number 2 311 435 describes a half-pixel motion estimation in accordance with this method.
It is an object of the invention to enable a cost reduction to be achieved.
In accordance with the invention, the degree of resemblance between a data sample and interpolations of another data sample with further data samples is determined in the following manner. In a preliminary calculation step a common portion is calculated. The common portion is K multiplied by the difference between the data sample and the other data sample multiplied by the first weighting factor, K being the inverse of the second weighting factor. In a further calculation step differences are calculated between the common portion and the respective further data samples. Each difference corresponds to the degree of resemblance between the data sample and the relevant interpolation.
The invention takes the following aspects into consideration. The greater the number of arithmetic operations a method comprises, the higher the cost to implement that method. For example, each arithmetic operation may be implemented by means of a specific item of hardware. If the method comprises relatively many arithmetic operations, its implementation will comprise relatively many items of hardware. The method may also be implemented by means of a single item of hardware: a processor that is programmed to carry out the method. In many applications the method should be carried out within a certain time limit. The processor will need to be relatively fast if the method comprises relatively many arithmetic operations. The faster a processor is, the more expensive the processor will be.
The prior-art method requires the following arithmetic operations. In principle, each interpolation involves at least two multiplications and one addition. There is one exception: if the weighting factors are both 0.5, one addition and one division by two will be sufficient. It requires one subtraction to calculate the difference between the relevant data sample and an interpolation. Supposing that there are N different interpolations, N being an integer, this means that 2N multiplications, N additions and N subtractions are required. If the weighting factors are both 0.5, N additions, N divisions and N subtractions will be sufficient.
The method in accordance with the invention requires the following arithmetic operations. In principle, the preliminary calculation step involves two multiplications and one subtraction. There is one exception: if the weighting factors are both 0.5, one multiplication and one addition will be sufficient. The further calculation step involves a subtraction for each interpolation. Supposing that there are N different interpolations, this means that two multiplications and N+1 subtractions are required. If the weighting factors are both 0.5, one multiplication and N+1 subtractions will be sufficient. Consequently, the method in accordance with the invention requires fewer arithmetic operations than the prior-art method. Consequently, the invention allows a cost reduction to be achieved.